1902D - Robot Queries - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
typedef pair<ll, ll> pll;

#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define MSV(X, V) memset((X), V, sizeof((X)))
#define LEN(X) strlen(X + 1)
#define SIZ(X) ((int)X.size())
#define MP make_pair
#define PB push_back
#define EB emplace_back

/* SORT_AND_UNIQUE */

template <class T>
void REV (T *a, int n) {
    reverse (a + 1, a + 1 + n);
}
template <class T>
void SRT (T *a, int n) {
    sort (a + 1, a + 1 + n);
}
template <class T>
int UNI (T *a, int n) {
    sort (a + 1, a + 1 + n);
    return unique (a + 1, a + 1 + n) - (a + 1);
}
template <class T>
int POS (T *a, int n, T v) {
    return lower_bound (a + 1, a + 1 + n, v) - a;
}
template <class T>
int fisrtGe (T *a, int n, T v) {
    return lower_bound (a + 1, a + 1 + n, v) - a;
}
template <class T>
int lastLe (T *a, int n, T v) {
    return upper_bound (a + 1, a + 1 + n, v) - a - 1;
}

/* READ_AND_WRITE */

template <class T>
void _RD (T &x) {
    cin >> x;
}
void _RD (int &x) {
    scanf ("%d", &x);
}
void _RD (uint &x) {
    scanf ("%u", &x);
}
void _RD (ll &x) {
    scanf ("%lld", &x);
}
void _RD (ull &x) {
    scanf ("%llu", &x);
}
void _RD (double &x) {
    scanf ("%lf", &x);
}
void _RD (char &x) {
    scanf (" %c", &x);
}
void _RD (char *x) {
    scanf ("%s", x + 1);
}
template<class T, class U>
void _RD (pair<T, U> &x) {
    _RD (x.first);
    _RD (x.second);
}
void RD() {
}
template <class T, class... U>
void RD (T &head, U &...tail) {
    _RD (head);
    RD (tail...);
}
template <class T>
void RDN (T *a, int n) {
    for (int i = 1; i <= n; ++i)
        _RD (a[i]);
}

template <class T>
void _WT (const T &x) {
    cout << x;
}
void _WT (const int &x) {
    printf ("%d", x);
}
void _WT (const uint &x) {
    printf ("%u", x);
}
void _WT (const ll &x) {
    printf ("%lld", x);
}
void _WT (const ull &x) {
    printf ("%llu", x);
}
void _WT (const double &x) {
    printf ("%.12f", x);
}
void _WT (const char &x) {
    putchar (x);
}
void _WT (const char *x) {
    printf ("%s", x + 1);
}
template <class T, class U>
void _WT (const pair<T, U> &x) {
    _WT (x.first);
    putchar (' ');
    _WT (x.second);
}
void WT() {
}
template <class T, class... U>
void WT (const T &head, const U &...tail) {
    _WT (head);
    putchar (sizeof... (tail) ? ' ' : '\n');
    WT (tail...);
}
template <class T>
void WTN (T *a, int n) {
    for (int i = 1; i <= n; ++i) {
        _WT (a[i]);
        putchar (" \n"[i == n]);
    }
}

template <class T>
void WTV (const vector<T> &x, bool ln = false) {
    WT (x.size());
    for (auto i = x.begin(); i != x.end(); ++i) {
        _WT (*i);
        putchar (ln ? '\n' : ' ');
    }
    if (!ln)
        putchar ('\n');
}

#ifdef LOCAL
#define D1(a)           cerr << #a << " = " << (a) << endl
#define D2(a, b)        cerr << #a << " = " << (a) << ", " << #b << " = " << (b) << endl
#define D3(a, b, c)     cerr << #a << " = " << (a) << ", " << #b << " = " << (b) << ", " \
                             << #c << " = " << (c) << endl
#define D4(a, b, c, d)  cerr << #a << " = " << (a) << ", " << #b << " = " << (b) << ", " \
                             << #c << " = " << (c) << ", " << #d << " = " << (d) << endl
#define ASSERT(x) assert(x)
#else
#define D1(a)
#define D2(a, b)
#define D3(a, b, c)
#define D4(a, b, c, d)
#define ASSERT(x)
#endif

/* CMIN_AND_CMAX */

template <typename T>
void cmin (T &x, T y) {
    if (y < x)
        x = y;
}

template <typename T>
void cmax (T &x, T y) {
    if (y > x)
        x = y;
}

//#ifdef LOCAL
//uint rnd_seed = 19937;
//#else
uint rnd_seed = chrono::duration_cast<chrono::nanoseconds> (
                    chrono::steady_clock::now().time_since_epoch()).count();
//#endif // LOCAL

mt19937 rnd (rnd_seed);

const int INF = 0x3F3F3F3F;
const ll LINF = 0x3F3F3F3F3F3F3F3FLL;
int MOD = 998244353;
/* MOD must be a prime. if not, don't use inv() */

struct ModularIntegers {
#define mint ModularIntegers
    int num;
    mint() {
        num = 0;
    }
    template <typename T>
    mint (const T& x) {
        ll tmp = x;
        if (tmp >= MOD) {
            if (tmp < (MOD << 1)) tmp -= MOD;
            else tmp %= MOD;
        } else if (tmp < 0) {
            if (tmp >= -MOD) tmp += MOD;
            else if (tmp %= MOD) tmp += MOD;
        }
        num = tmp;
    }
    friend mint operator+ (const mint &x, const mint &y) {
        mint res;
        res.num = x.num + y.num;
        if (res.num >= MOD) res.num -= MOD;
        return move (res);
    }
    friend mint operator- (const mint &x, const mint &y) {
        mint res;
        res.num = x.num - y.num;
        if (res.num < 0) res.num += MOD;
        return move (res);
    }
    friend mint operator* (const mint &x, const mint &y) {
        mint res;
        res.num = 1LL * x.num * y.num % MOD;
        return move (res);
    }
    friend mint operator/ (const mint &x, const mint &y) {
        return x * y.inv();
    }
    friend bool operator== (const mint &x, const mint &y) {
        return x.num == y.num;
    }
    friend bool operator!= (const mint &x, const mint &y) {
        return x.num != y.num;
    }
    mint operator+() {
        return +this->num;
    }
    mint operator-() {
        return -this->num;
    }
    mint& operator+= (const mint &x) {
        if ( (this->num += x.num) >= MOD) this->num -= MOD;
        return *this;
    }
    mint& operator-= (const mint &x) {
        if ( (this->num -= x.num) < 0) this->num += MOD;
        return *this;
    }
    mint& operator*= (const mint &x) {
        this->num = 1LL * this->num * x.num % MOD;
        return *this;
    }
    mint& operator/= (const mint &x) {
        this->num = ( (*this) * x.inv()).num;
        return *this;
    }
    mint pow (ll x) const {
        mint res (1), cur (this->num);
        for (; x; cur *= cur, x >>= 1)
            if (x & 1) res *= cur;
        return res;
    }
    mint inv() const {
        return pow (MOD - 2);
    }
    operator int() {
        return num;
    }
    operator uint() {
        return num;
    }
    operator ll() {
        return num;
    }
    operator ull() {
        return num;
    }
#undef mint
};

typedef ModularIntegers mint;

void _RD (mint &x) {
    scanf ("%d", &x.num);
}
void _WT (const mint &x) {
    printf ("%d", x.num);
}

struct custom_hash {
    static uint64_t splitmix64 (uint64_t x) {
        x ^= x << 13;
        x ^= x >> 7;
        x ^= x << 17;
        return x;
    }
    size_t operator () (uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); // 时间戳
        return splitmix64 (x + FIXED_RANDOM);
    }
};

/*****************/
/* MY_CODE_BEGIN */


static const int MAXN = 2e5 + 10;

int n;
char s[MAXN];
int x[MAXN];
int y[MAXN];
int rx[MAXN];
int ry[MAXN];

struct my_map {
    vector<pair<pii, int>> vec;


    void clear() {
        vec.clear();
    }

    int count (const pii & key) {
        auto it = lower_bound (vec.begin(), vec.end(), make_pair (key, -INF));
        return it == vec.end() ? 0 : it->first == key ? 1 : 0;
    }

    void init() {
        sort (vec.begin(), vec.end());
        vec.resize (unique (vec.begin(), vec.end()) - vec.begin());
    }

    void insert (const pii & key, int value) {
        vec.push_back ({key, value});
    }

    int get (const pii & key) {
        auto it = lower_bound (vec.begin(), vec.end(), make_pair (key, -INF));
        return it ->second;
    }


};

static constexpr int calc_segment_tree_size (int n) {
    int res = 1;
    while (res < (n << 1)) {
        res <<= 1;
    }
    return res;
}

struct SegmentTree {

#define ls (u << 1)
#define rs (u << 1 | 1)
#define mid ((l + r) >> 1)

    static constexpr int MAXN_SEGMENT_TREE_SIZE = calc_segment_tree_size (MAXN);

    int n;
    my_map sum[MAXN_SEGMENT_TREE_SIZE];
    int preculX[MAXN];
    int preculY[MAXN];

    void pushUp (int u, int l, int r) {
        sum[u].clear();
        for (auto nd : sum[ls].vec) {
            sum[u].insert (nd.first, nd.second);
        }
        for (auto nd : sum[rs].vec) {
            auto t = nd.first;
            int x = t.first + iCul (l, mid).first;
            int y = t.second + iCul (l, mid).second;
            if (sum[u].count ({x, y}) == 0) {
                sum[u].insert (pii (x, y), nd.second);
            }
        }
        sum[u].init();
    }

    void iCulInit (int n) {
        for (int i = 1; i <= n; ++i) {
            preculX[i] = preculX[i - 1] + x[i];
            preculY[i] = preculY[i - 1] + y[i];
        }
    }

    void iBuild (int u, int l, int r) {
        if (l > r) {
            return;
        }
        if (l == r) {
            sum[u].clear();
            sum[u].insert (pii (0, 0), l - 1);
            sum[u].insert (pii (x[l], y[l]), l);
            sum[u].init();
        } else {
            iBuild (ls, l, mid);
            iBuild (rs, mid + 1, r);
            pushUp (u, l, r);
        }
    }

    // 查询[L,R]区间内的累积操作，从00开始是否经过dx，dy
    ll iContain (int u, int l, int r, int L, int R, int dx, int dy) {
        if (L > R) {
            return 0;
        }
        ll res = 0;

        if (l == L) {
            // 左端点相同的时候，如果整个区间不包含，直接废除掉。
            if (sum[u].count ({dx, dy}) == 0) {
                return 0;
            }
            int minid = sum[u].get ({dx, dy});
            return minid <= R;
        }

        res = iContain (ls, l, mid, L, min (mid, R), dx, dy);
        if (res == 1) {
//            D4 (L, R, dx, dy);
//            D1 (res);
            return res;
        }

        pii culLs = iCul (L, min (mid, R));

        // 从culX[ls],culY[ls]开始，经过dx - culX[ls], dy-culY[ls] = 经过dx，dy
        res = iContain (rs, mid + 1, r, max (mid + 1, L), R, dx - culLs.first, dy - culLs.second);

//        D4 (L, R, dx, dy);
//        D1 (res);
        return res;
    }

    pii iCul (int L, int R) {
        if (L > R) {
            return {0, 0};
        }
        return {preculX[R] - preculX[L - 1], preculY[R] - preculY[L - 1]};
//        pii res = {0, 0};
//        if (l > r || L > R || L > r || R < l) {
//            return res;
//        }
//        if (l == L && r == R) {
//            res = {culX[u], culY[u]};
//            return res;
//        }
//
//        pii resL = iCul (ls, l, mid, L, min (mid, R));
//        res.first += resL.first;
//        res.second += resL.second;
//
//        pii resR = iCul (rs, mid + 1, r, max (mid + 1, L), R);
//        res.first += resR.first;
//        res.second += resR.second;
//        return res;
    }

#undef ls
#undef rs
#undef mid

} tree, rtree;


void solve() {
    int q;
    RD (n, q, s);
    for (int i = 1; i <= n; ++i) {
        if (s[i] == 'U') {
            x[i] = 0;
            y[i] = +1;
        }
        if (s[i] == 'D') {
            x[i] = 0;
            y[i] = -1;
        }
        if (s[i] == 'R') {
            x[i] = +1;
            y[i] = 0;
        }
        if (s[i] == 'L') {
            x[i] = -1;
            y[i] = 0;
        }
    }
    tree.iCulInit (n);
    tree.iBuild (1, 1, n);

    reverse (s + 1, s + 1 + n);
    for (int i = 1; i <= n; ++i) {
        if (s[i] == 'U') {
            x[i] = 0;
            y[i] = +1;
        }
        if (s[i] == 'D') {
            x[i] = 0;
            y[i] = -1;
        }
        if (s[i] == 'R') {
            x[i] = +1;
            y[i] = 0;
        }
        if (s[i] == 'L') {
            x[i] = -1;
            y[i] = 0;
        }
    }
    rtree.iCulInit (n);
    rtree.iBuild (1, 1, n);

    while (q--) {
        int qx, qy, l, r;
        RD (qx, qy, l, r);
//        WT (qx, qy, l, r);

        if (tree.iContain (1, 1, n, 1, l - 1, qx, qy)) {
            puts ("YES");
            continue;
        }
        pii cul = tree.iCul (1, l - 1);
        int culX = cul.first;
        int culY = cul.second;
//        D2 (culX, culY);

        // [l, r] 反转之后，i变成n-i+1
        // [n-r+1, n - l + 1]

        if (rtree.iContain (1, 1, n, n - r + 1, n - l + 1, qx - culX, qy - culY)) {
            puts ("YES");
            continue;
        }

        pii cul2 = rtree.iCul (n - r + 1, n - l + 1);
        int culX2 = cul2.first;
        int culY2 = cul2.second;
//        D2 (culX2, culY2);

        // [l, r] 反转之后，i变成n-i+1
        // [n-r+1, n - l + 1]

        if (tree.iContain (1, 1, n, r + 1, n, qx - culX - culX2, qy - culY - culY2)) {
            puts ("YES");
            continue;
        }
        puts ("NO");
//        puts ("NO");
    }

//    RDN (a, n);
    // 通过前缀和，可以知道前i步访问的节点的集合
    // 数据结构，支持查询(x,y)，知道第一次到达x,y位置的步数

    // 区间反转，前面l-1位置保持不变，查询xy是否小于等于l-1
    // 否则，结束点为x[l-1], y[l-1]，相对偏移为x-x[l-1],y-y[l-1]，为dxdy

    // 否则，取出一个相反的操作序列，在相反的操作序列中，对应[l,r]区间的是
    // [n - r, n - r + (r - l + 1)] 这个区间中经过了哪些点？

    // 查询以n-r为起点00的时候，是否在(r - l + 1)内经过了dxdy？

    // 否则结束点为xx，yy，相对偏移dx2，dy2，故技重施

    // 也就是需要一组相反的数据结构，满足查询[L,R]区间内，从00开始这些区间的操作累积是否经过xy

    // 很难，如果是查询[L,R]区间

    // 分块，好像可以做，每个400大小的区间存储从左端点开始的经过的坐标的位移set
    // 总共存储2e5个坐标

    // 然后从左到右，满400的就在set里面找，不满的就一个一个累积

    // 然后回放操作，算出终结节点。

    // 那何必分块，线段树就行了。

    // 线段树，每个node存自己的子树从00开始回放经过的节点，每层2e5，共log层
    //20*2e5*4bit=16e6=16MB

    // 然反向16MB


}


int main() {
    int t = 1;
#ifdef LOCAL
    freopen ("A.in", "r", stdin);
    RD (t);
#endif // LOCAL
    cout << fixed << setprecision (12);
    cerr << fixed << setprecision (12);
//    ios::sync_with_stdio (false);
//    cin.tie (nullptr);
//    cout.tie (nullptr);
    for (int i = 1; i <= t; ++i) {
//        printf ("Case #%d: ", i);
        solve();
    }
    puts ("");
    return 0;
}
//